package book_mianshizhinan.test1_5;

import java.util.Stack;

public class SortStackByStack {
	
	
	public static void main(String[] args) {
		Stack <Integer>stack = new Stack<Integer>();
		stack.push(1);
		stack.push(5);
		stack.push(3);
		sortStackByStack(stack);
		System.out.println(stack.toString());
	}

	public static Stack<Integer> sortStackByStack(Stack<Integer> stack) {

		Stack<Integer> newStack = new Stack<Integer>();
		while(!stack.empty()){
			int curr = stack.pop();
			if(newStack.empty()){
				newStack.push(curr);
			}else{
				int top = newStack.peek();
				while(curr>top&&!newStack.empty()){//С������ջ����յģ�����û��topԪ��
					//�����и��򵥵ķ�����( ��-�� )
					stack.push(newStack.pop());
					if(newStack.empty()){
						top = 0;
					}else{
						top = newStack.peek();
					}
				}
				newStack.push(curr);
			}
		}
		
		while(!newStack.empty()){
			stack.push(newStack.pop());
		}
		
		
		return stack;

	}

}
